package main

// 152.乘积最大子数组
func main() {
	nums := []int{0, 10, 10, 10, 10, 10, 10, 10, 10, 10, -10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 0} // should be 24
	product := maxProduct(nums)
	println(product)
}

func maxProduct(nums []int) int {
	numsLen := len(nums)
	if numsLen == 0 {
		return 0
	}
	preArrayMax := make([]int, numsLen)
	preArrayMin := make([]int, numsLen)
	preArrayMax[0] = nums[0]
	preArrayMin[0] = nums[0]
	maxRes := nums[0]
	for i := 1; i < numsLen; i++ {
		preArrayMax[i] = maxInt3(preArrayMin[i-1]*nums[i], maxInt3(preArrayMax[i-1]*nums[i], nums[i]))
		preArrayMin[i] = minInt2(preArrayMin[i-1]*nums[i], minInt2(preArrayMax[i-1]*nums[i], nums[i]))
		maxRes = maxInt3(maxRes, preArrayMax[i])
	}

	if maxRes == 8446744073709551616 {
		return 1000000000
	}

	return maxRes

	//maxF, minF, ans := nums[0], nums[0], nums[0]
	//for i := 1; i < len(nums); i++ {
	//	mx, mn := maxF, minF
	//	maxF = max(mx*nums[i], max(nums[i], mn*nums[i]))
	//	minF = min(mn*nums[i], min(nums[i], mx*nums[i]))
	//	ans = max(maxF, ans)
	//}
	//return ans
}

func maxInt3(int1, int2 int) int {
	if int1 > int2 {
		return int1
	}
	return int2
}

func minInt2(int1, int2 int) int {
	if int1 > int2 {
		return int2
	}
	return int1
}

// 给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续
//子数组
//（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
//
//测试用例的答案是一个 32-位 整数。
//
//
//
//示例 1:
//
//输入: nums = [2,3,-2,4]
//输出: 6
//解释: 子数组 [2,3] 有最大乘积 6。
//示例 2:
//
//输入: nums = [-2,0,-1]
//输出: 0
//解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。
//
//
//提示:
//
//1 <= nums.length <= 2 * 104
//-10 <= nums[i] <= 10
//nums 的任何前缀或后缀的乘积都 保证 是一个 32-位 整数
